package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/23
 * @description: 198. 打家劫舍
 * https://leetcode-cn.com/problems/house-robber/
 */
public class B_198_打家劫舍 {

	public static void main(String[] args) {


	}

	/**
	 * 这个跟股票问题没有区别：
	 * 由于每一间屋子都有两种状态：被打劫 or 不被打劫
	 * dp[i][0] 表示：不被打劫；
	 * dp[i][1] 表示：被打劫；
	 * dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
	 * dp[i][1] = dp[i-1][0]+nums[i]
	 * @param nums
	 * @return
	 */
	public int rob(int[] nums) {
		int len = nums.length;
		if (len==0){
			return 0;
		}
		int[][] dp =new int[len][2];
		dp[0][0]=0;
		dp[0][1]=nums[0];
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i]);
			dp[i][1] = dp[i - 1][0] + nums[i];
		}
		return Math.max(dp[len - 1][0], dp[len - 1][1]);
	}
}
